/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/minimum-window-substring
   @Language: C++
   @Datetime: 19-03-11 10:12
   */

// Method 1, Time 50ms
class Solution {
public:
	/**
	 * @param source : A string
	 * @param target: A string
	 * @return: A string denote the minimum window, return "" if there is no such a string
	 */
	string minWindow(string &source , string &target) {
		// write your code here
		unordered_map<char,int> dict, win;
		for(char c:target)
			dict[c]++;
		int begin=-1, end=source.length();
		queue<int> q;   // fast skip i
		for(int i=-1, j=0; j<source.length();){
			if(dict.find(source[j])!=dict.end()){
				win[source[j]]++;
				if(match(win,dict)){
					if (j-i<end-begin) begin=i, end=j;
					win[source[i]]--;
					win[source[j]]--;
					i=q.front();
					q.pop();
				}
				else q.push(j++);
			}
			else ++j;
		}
		if (end==source.length()) return "";
		return source.substr(begin,end-begin+1);
	}
	bool match(unordered_map<char,int> &win, unordered_map<char,int> &dict){
		for(pair<char,int> p:dict)
			if (win[p.first]<p.second) return false;
		return true;
	}
};
